package 力扣.栈;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

public class 下一个更大元素I496 {
    public static void main(String[] args) {
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1,3,4,2};
        int[] ints = nextGreaterElement2(nums1, nums2);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 方法一：直接先使用hashmap 映射出nums2中每一个元素的位置，然后遍历nums1,根据hashmap查找其在nums2中的索引位置，最后在索引的右边寻找nums1[i]大的值
     */
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums2.length; i++) {
            hashMap.put(nums2[i],i);
        }
        for (int i = 0; i < nums1.length; i++) {
            int te = nums1[i];
            Integer index = hashMap.get(te);
            int flag = 0;
            for (int j = index; j < nums2.length; j++) {
                int te2 = nums2[j];
                if (te2 > te){
                    ans[i] = te2;
                    flag = 1;
                    break;
                }
            }
            if (flag == 0){
                ans[i] = -1;
            }
        }
        return ans;
    }

    /**
     *方法二：先忽略nums1,在nums2中寻找右边第一个比它大的元素，然后将元素和右边第一个比它大的元素放入哈希表中。最后遍历nums1，查找哈希表即可。
     */
    public static int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        Deque<Integer> deque = new LinkedList<>();
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int te: nums2) {
            while (!deque.isEmpty() && deque.peek() < te){
                hashMap.put(deque.pop(), te);
            }
            deque.push(te);
        }
        while (!deque.isEmpty()){
            hashMap.put(deque.pop(),-1);
        }
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = hashMap.get(nums1[i]);
        }
        return nums1;
    }

}
